// 树状数组 差分数组 i d[i]
// https://www.luogu.com.cn/problem/P3372

int n, q;
ll a[maxn], c[2][maxn]; // c[0][i] for d[i], c[1][i] for i * d[i]
// sum(a[1], a[n]) = (n + 1) * sum(d[1], d[n]) - sum(f[1], f[n]), f[i] = i * d[i]

void update(int i, int k, ll *tr) { // 树状数组的单点修改
    while (i <= n) {
        tr[i] += k;
        i += i & -i;
    }
}

void update(int l, int r, int k) { // 区间修改
    update(l, k, c[0]), update(r + 1, -k, c[0]);
    update(l, l * k, c[1]), update(r + 1, -(r + 1) * k, c[1]);
}

ll pre(int i) { // 前缀区间查询，返回 sum(a[1], a[i])
    ll ret = 0, tmp = i + 1;
    while (i >= 1) {
        ret += tmp * c[0][i];
        ret -= c[1][i];
        i -= i & -i;
    }
    return ret;
}
